package com.maltys.dp.backpack;

import java.util.Arrays;

/**
 * left - rght = target
 * left + right = sum
 * <p>
 * left = (target + sum)/2
 *
 * @author malty
 * @link <a href="https://leetcode.cn/problems/target-sum/description/">目标和</a>
 */
public class TargetSum {
    public static void main(String[] args) {
        TargetSum targetSum = new TargetSum();
        /**
         * 0 1 0 0
         * 0 0 1 0
         * 0 3 3 1
         * 0 0 6 3
         * 0 24 0 5
         * dp[4][4]+dp[4][2]
         */
        int sum = targetSum.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 5);
        System.out.println(sum);
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if ((sum + target) % 2 != 0 || sum + target < 0) {
            return 0;
        }
        int[][] dp = new int[nums.length + 1][(sum + target) / 2 + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= (sum + target) >> 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][(sum + target) / 2];
    }
}
